Wesołe miasteczko

Limit pamięci: 64 MB

Bajtazar i Bajtoni wybrali się do wesołego miasteczka. Odwiedzali to miejsce już wiele razy i dobrze znają wszystkie atrakcje, dlatego każdy z nich przygotował zawczasu listę swoich ulubionych atrakcji, które chciałby po kolei odwiedzić. Listy różniły się od siebie, dlatego przyjaciele zdecydowali się wykreślić z nich niektóre pozycje, tak, by stały się one identyczne. Nie chcą przy tym zmieniać oryginalnej kolejności z każdej z list. Dodatkowo, chcieliby, aby uzgodniony plan był najdłuższy możliwy. Ile różnych planów mogą w ten sposób uzyskać?

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i (), oznaczające długości planów Bajtazara i Bajtoniego. Kolejne dwa wiersze zawierają listy atrakcji zaproponowane przez każdego z nich. Są to listy liczb całkowitych z przedziału pooddzielanych pojedynczymi odstępami, długości odpowiednio i . Każda liczba określa jedną atrakcję w wesołym miasteczku.

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia wypisz jedną liczbę całkowitą. Powinna to być liczba różnych planów zwiedzania wesołego miasteczka, które mogą utworzyć przyjaciele poprzez wykreślanie pozycji z zaproponowanych przez siebie list atrakcji modulo .

Przykład

Dla danych wejściowych:

4 5
1 2 3 1
1 1 3 2 1

poprawną odpowiedzią jest:

2

Autor zadania: Jakub Łącki.